package algotithm.weekendrace.leetcode231.test3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author zhouyanxiang
 * @Date 2021-03-2021/3/7-10:29
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
    }

    long MOD = (long) 1e9 + 7;
    long [] dp;
    ArrayList<int[]> graph[];
    long[] dist;
    int n;
    public int countRestrictedPaths(int n, int[][] edges) {
        this.n = n;
        dp = new long[n + 1];
        graph = new ArrayList[n + 1];
        dist = new long[n + 1];
        Arrays.fill(dp, -1);
        Arrays.fill(dist, -1);
        for(int i = 1; i <= n; i++) {
            graph[i] = new ArrayList();
        }
        for(int[] edge : edges) {
            int u = edge[0], v = edge[1], d = edge[2];
            graph[u].add(new int[]{v, d});
            graph[v].add(new int[]{u, d});
        }
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>( (p1, p2) -> p1[1] - p2[1]);
        pq.add(new int[]{n, 0});
        //System.out.println("pq: " + pq);
        while(!pq.isEmpty()) {
            int[] cur = pq.poll();
            int node = cur[0], dis = cur[1];
            if(dist[node] != -1) {
                continue;
            }
            dist[node] = dis;
            for(int[] edge : graph[node]) {
                pq.add(new int[]{edge[0], dis + edge[1]});
            }
        }
        int res =  (int) f(1);
        //System.out.println("dp: " + Arrays.toString(dp));
        //System.out.println("dist: " + Arrays.toString(dist));
        return res;
    }
    long f(int i) {
        //System.out.println(i + " cur dp: " + dp[i]);
        if(dp[i] != -1) {
            return dp[i];
        }
        if(i == n) {
            return 1;
        }
        long res = 0L;
        for(int[] edge : graph[i]) {
            if(dist[edge[0]] < dist[i]) {
                res += f(edge[0]);
            }
        }
        res %= MOD;
        return dp[i] = res;
    }
}
